package chapter03_binaryTree;

import com.sun.crypto.provider.PBEWithMD5AndDESCipher;
import sun.misc.InnocuousThread;

/**
 * 描述：
 *      判断是否是一颗平衡二叉树
 * @author hl
 * @date 2021/5/29 9:31
 */
public class IsBalance {

    /**
     * 将子树是否是平衡二叉树的字段放到递归函数的参数列表中，将子树高度的字段作为返回值
     * @param head
     * @return
     */
    public boolean isBalance(Node head){
        boolean[] res = new boolean[1];
        res[0] = true;
        getHeight(head, 1, res);
        return res[0];
    }

    private int getHeight(Node head, int level, boolean[] res) {
        if (head == null) {
            return level;
        }
        int lh = getHeight(head.left, level + 1, res);
        if (!res[0]) {
            return level;
        }
        int rh = getHeight(head.right, level + 1, res);
        if (!res[0]) {
            return level;
        }
        if (Math.abs(lh - rh) > 1) {
            res[0] = false;
        }
        return Math.max(lh, rh);
    }


    /**
     * 定义结构体封装返回格式，包含两个字段：
     *      1）子树是否为平衡二叉树。   用于提前结束无效递归
     *      2）子树的最大高度。  用于判断是否是平衡二叉树
     * @param head
     * @return
     */
    public boolean isBalance2(Node head){
        ReturnType r = process(head);
        return r.isBalance;
    }

    private ReturnType process(Node head) {
        if (head == null) {
            return new ReturnType(true, 0);
        }
        ReturnType lr = process(head.left);
        ReturnType rr = process(head.right);
        if (!lr.isBalance || !rr.isBalance || Math.abs(lr.height - rr.height) > 1) {
            return new ReturnType(false, -1);
        }
        return new ReturnType(true, Math.max(lr.height, rr.height));
    }

    static class ReturnType{
        boolean isBalance;
        int height;

        public ReturnType(boolean isBalance, int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }
}
